package com.person.leetcode.editor.cn;

import sun.reflect.generics.tree.Tree;

import java.util.Stack;

/**
 * 面试题 04.06.后继者
 * 2022-05-16 10:35:19
 **/
public class Sequence_SuccessorLcci {
    public static void main(String[] args) {
//        Solution solution = new Sequence_面试题 04.06_SuccessorLcci().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     */
    //不是普通的二叉树!!! 是二叉搜索树 排序树
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    class Solution {
        public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            //常规遍历,双指针指定后继者
            TreeNode prev = null, curr = root;
            while (!stack.isEmpty() || curr != null) {
                //遍历左子树,入栈
                while (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                }
                curr = stack.pop();
                if (prev == p) {
                    return curr;
                }
                prev = curr;
                curr = curr.right;
            }
            return null;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
